package offer;

import java.util.ArrayList;
import java.util.List;

public class offer34 {
}
class Solution34 {
    public static List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> track = new ArrayList<>();
        if(root==null)
            return new ArrayList<>();
        track.add(root.val);
        int i = 1;
        traverse(root,target-root.val,res,track,i);
       return res;
    }

    private static void traverse(TreeNode root, int target, List<List<Integer>> res, List<Integer> track,int i) {
      if(root.left==null&&root.right==null&&target==0)
      {
          res.add(new ArrayList<>(track));
          return;
      }
      if(root.left==null&&root.right==null) return;
      if(root.left!=null)
      {
          track.add(i,root.left.val);
          traverse(root.left,target-root.left.val,res,track,i+1);
          track.remove(i);

      }
      if(root.right!=null)
      {
          track.add(i,root.right.val);
          traverse(root.right,target-root.right.val,res,track,i+1);
          track.remove(i);
      }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode root1 = new TreeNode(2);
        TreeNode root2 = new TreeNode(3);
        root.left = root1;
        root.right = root2;
        pathSum(root,4);
    }
}